/**
 * @Title: QuickSort.java
 * @Package com.adamjwh.sort.quicksort
 * @Description: 
 * @author adamjwh
 * @date 2018年6月24日
 * @version V1.0
 */
package com.adamjwh.sort.quicksort;

/**
 * @ClassName: QuickSort
 * @Description: 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * @author adamjwh
 * @date 2018年6月24日
 * @时间复杂度：最优：O(nlogn) / 最坏：O(n^2)
 */
public class QuickSort {
	
	/**
	 * 
	 * @Title: partition
	 * @Description: 将数组的某一段元素进行划分，小的在左边，大的在右边
	 * @param @param arr
	 * @param @param start
	 * @param @param end
	 * @param @return    返回基准值所在的位置
	 * @return int    返回类型
	 * @throws
	 */
	public static int partition(int[] arr, int low, int high) {
//		int key = QuickSort_SelectKey.selectPivot(arr, low, high);	//以最左边的元素为基准值
//		int key = QuickSort_SelectKey.selectPivotRandom(arr, low, high);	//随机选取基准值
		int key = QuickSort_SelectKey.SelectPivotMedianOfThree(arr, low, high);	//三数取中法选取基准值
		
		while(low < high) {	//一旦low==high，说明左右两个指针合并到了同一位置，可以结束此轮循环
			while(low<high && arr[high]>=key) {	//从后半部分向前扫描
				high --;
			}
			//上方循环结束，说明当前arr[high]的值比基准值小
			arr[low] = arr[high];
			
			while(low<high && arr[low]<=key) {	//从前半部分向后扫描
				low ++;
			}
			//上方循环结束，说明当前arr[low]的值比基准值大
			arr[high] = arr[low];
		}
		arr[low] = key;	//存入基准
		
		return low;
	}
	
	/**
	 * 
	 * @Title: sort
	 * @Description: 排序
	 * @param @param arr
	 * @param @param low
	 * @param @param high    参数
	 * @return void    返回类型
	 * @throws
	 */
	public static void sort(int[] arr, int low, int high) {
		if(low >= high) {	//只有一个元素，不需要排序
			return;
		}
		
		if(high-low+1 < 10) {	//待排序序列长度小于10，使用插入排序
			InsertSort.insertSort(arr);
			return;
		}
		
		int index = partition(arr, low, high);	//第一轮排序获取分割点（基准值）
		sort(arr, low, index-1);	//排序前半部分
		sort(arr, index+1, high);	//排序后半部分
	}
	
	/**
	 * 
	 * @Title: main
	 * @Description: 主函数（测试函数）
	 * @param @param args    参数
	 * @return void    返回类型
	 * @throws
	 */
	public static void main(String[] args) {
		int[] arr = new int[] {49, 38, 65, 97, 76, 13, 27};
		
		/**
		 * 第一轮（key=49）：  49  38  65  97 76 13  27
		 * 	从右（49>27）：    [27] 38  65  97 76 13  27
		 * 	从左（49<65）：     27  38  65  97 76 13 [65]
		 *  从右（49>13）：     27  38  [13] 97 76 13  27
		 *  从左（49<97）：     27  38  13  97  76 [97] 27
		 * 	存基准：		    27  38  13 [49] 76  97  65
		 */
		sort(arr, 0, arr.length-1);	//快排
		
		for (int i : arr) {	//输出
			System.out.print(i + " ");
		}
	}

}
